package com.yitiao.data_algorithms.leetcode.editor.cn;

class UniqueBinarySearchTrees {
    // 2023-02-09 13:31:34
    public static void main(String[] args) {
        Solution solution = new UniqueBinarySearchTrees().new Solution();
        solution.numTrees(3);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 当提示有数学的时候，尝试找规律并用动态规划求解
        // n=1  1种
        // n=2  2种
        // n=3  5种
        // dp[i] += dp[j - 1] * dp[i - j]; ，
        // j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量
        public int numTrees(int n) {
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
                for (int j = 1; j <= i; j++) {
                    dp[i] += dp[j - 1] * dp[i - j];
                }
            }
            return dp[n];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}